#include "stdio.h"

/*int candidate(int length, int* attr)
{
	if (length <= 0)
		return -1;
	printf("%d \n", length);
	int end = length - 1;
	int usefull = 0;
	int i = 0;
	while(end >=1)
	{
		i = 0;
		usefull = 0;
		for(i = 0; i < end;)
		{
			if (attr[i] == attr[i + 1])
			{
				attr[usefull] = attr[i];
				usefull++;
			}
			i = i + 2;
			//odd number
			if(i  == end)
			{
				attr[usefull] = attr[i];
				usefull ++;
			}
			printf("%d %d\n", i, usefull);
		}

		end = usefull - 1;
		printf("end %d\n", end);

		for (int j = 0; j <= end; ++j)
		{
			printf("%d\n", attr[j]);
		}
	}

	if (end == 0)
		return attr[0]; 
	return -1;
}*/

int candidate(int* attr, int length)
{
	int pass_length = 0;
	int i = 0;
	if(length<0 | attr == NULL)
	{
		return -1;
	}
	if (length == 1)
		return attr[0];

	for(i = 0; i < length;i++)
		printf("%d\n", attr[i]);
	// even number
	// repeat once
	if (length %2)
	{
		printf("step1\n");
		for (i = 0; i < length - 1; )
		{
			if(attr[i] == attr[i + 1])
			{
				attr[pass_length] = attr[i];
				pass_length++;
			}
			i = i + 2;
		}
		for(i = 0; i < pass_length;i++)
			printf("%d\n", attr[i]);


		printf("step2\n");
		if (attr[length - 1] == attr[0])
		{
			attr[pass_length] = attr[i];
			pass_length++;
		}
		for(i = 0; i < pass_length;i++)
			printf("%d\n", attr[i]);

		printf("step3\n");
		for (i = 1; i < length; )
		{
			if(attr[i] == attr[i + 1])
			{
				attr[pass_length] = attr[i];
				pass_length++;
			}
			i = i + 2;
		}
		for(i = 0; i < pass_length;i++)
			printf("%d\n", attr[i]);
		// all are the same
		if(pass_length == length)
			return attr[0];
	}
	//odd number
	else
	{
		for (i = 0; i < length;)
		{
			if(attr[i] == attr[i + 1])
			{
				attr[pass_length] = attr[i];
				pass_length++;
			}
			i = i + 2;
		}
		
	}
	return candidate(attr, pass_length);
}
bool isMajority(int c, int length, int* attr)
{
	printf("Call isMajority\n");
	int count = 0;
	for (int i = 0; i < length; ++i)
	{
		if (attr[i] == c)
			count ++;
	}

	if (count > int(length/2 + 0.5))
	{
		return true;
	}
	return false;
}

int main(int argc, char const *argv[])
{
	const int length = 3;
	int a[length] = {1,1,1};
	int b[length] = {1,1,1};
	int result = -1;
	int index = 0;
	int number = 1;
	int i = 0;

	printf("test start\n");
	while(1)
	{	
		printf("==a==\n");
		for (i = 0; i < length; ++i)
		{
			printf("%d ", a[i]);
			b[i] = a[i];
		}
		printf("\n");

		result = candidate(b, length);
		if (result >= 0)
		{
			printf("candidate %d\n", result);
			if (isMajority(result,length,b))
				printf("%d is the majority number\n", result);
			else
				printf("no majority number\n");
		}
		else 
			printf("no candidate\n");
		//end condition
		if(index >= length)
		{
			printf("test finished\n");
			break;
		}
			
		if(number < length - 1)
		{
			a[index] = ++number;
		}	
		else
		{
			while(a[index] >= (length -1) & index < length)
				index++;
			if(index >= length)
			{
				printf("test finished\n");
				break;
			}
			a[index]++;
			while((--index) + 1 )
			{
				a[index] = 1;
			}
			index = 0;
			number = 1;				
		}
	}
	return 0;
}